import java.util.Arrays;

/**
 * @author ChenJunhong
 * @date 2018/10/30
 * Description:
 * 冒泡排序算法的实现
 *
 * （1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
 *
 * （2）这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
 *
 * （3）N=N-1，如果N不为0就重复前面二步，否则排序完成。
 *
 */
public class BubbleSort {


    /**
     * 最普通的冒泡排序算法
     * @param arr
     */
    public static void bubbleSort1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            // 在进行了第 i 次比较以后，最大的数据在 arr.length-i 处
            // 这个点相当于是个终点--在这个点以后的数据，都不需要在进行比较了，因为这个点以后的数据都已经排序过了
            for (int j = 1; j < arr.length - i; j++) {
                // 如果前面的数字比较大，将他移到后面去
                if(arr[j-1] > arr[j]){
                    swap(arr,j-1,j);
                }
            }
        }
    }


    /**
     * 加上了flag的冒泡排序
     * 对于一个大部分数据已经排序了数组，则不需要进行大量的比较以及交换。
     * 那么可以设置一个flag，如果这个flag为flase，即没有产生交换，那么就意味着排序已经完成了。
     * @param arr
     */
    public static void bubbleSort2(int[] arr){

        // 初始化这个flag
        boolean flag = true;

        // 需要进行比较的边界点，初始值为数组的长度
        int bound = arr.length;

        while (flag){
            flag = false;
            for (int i = 1; i < bound  ; i++) {
                if (arr[i-1] > arr[i]){
                    swap(arr,i-1,i);
                    flag = true;
                }
            }
            // 每次比较完，都减小一次边界
            bound--;
        }
    }


    /**
     * 交换数组中的数据的位子
     * @param arr
     * @param x
     * @param y
     */
    public static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {89,54,15,25,34,8,45,6,78,44,1};
        bubbleSort1(arr);
        //bubbleSort2(arr);
        System.out.println(Arrays.toString(args));
    }


}
